// https://www.lintcode.com/problem/minimum-window-substring/my-submissions

class Solution {
public:
    /**
     * @param source : A string
     * @param target: A string
     * @return: A string denote the minimum window, return "" if there is no such a string
     */
    string minWindow(string &source , string &target) {
        // write your code here  
        if (target.empty() || source.empty())
            return "";
        map<char, int> targ; // 可以用一个cnt来记录不是0的个数。直接删除的话map底层红黑树log(n)
        for (char c: target)
        {
            targ[c]++;
        }
        int cnt = targ.size();
        int n = source.length();
        int res = INT_MAX;
        int start = 0;
        for (int l = 0, r = 0; r < n; ++r)
        {
            // if (targ.find(source[r]) != targ.end()) 其实有了对cnt是否为0或1的判断，这个可以去掉
            // {
                targ[source[r]]--;
                if (targ[source[r]] == 0)
                    cnt--;
            // }
            while (!cnt)
            {
                if (r - l + 1 < res)
                {
                    res = r - l + 1;
                    start = l;
                }
                // if (targ.find(source[l]) != targ.end()) 
                // {
                    // cnt++; 可能减成负数了，不要急着加
                    // Input
                    // "aaaaaaaaaaaabbbbbcdd"
                    // "abcdd"
                    // Output
                    // "aaaaaaaaaaaabbbbbcdd"
                    // Expected
                    // "abbbbbcdd"
                    targ[source[l]]++;
                    // if (targ[source[l]] > 0)不行，会重复加
                    if (targ[source[l]] == 1)
                        cnt++;
                    // l++; 无论如何都要加，放外面
                // }
                l++;
            }
        }
        return res == INT_MAX ? "": source.substr(start, res);
    }
};


class Solution {
public:
    /**
     * @param source : A string
     * @param target: A string
     * @return: A string denote the minimum window, return "" if there is no such a string
     */
    // map里直接就减成负数，这样也能记录source里面的情况，不用根据target来判断左指针移动的时候需不需要改map
    string minWindow(string &source , string &target) {
        map<char, int> rec;
        int sum = 0;
        int start = 0;
        int end = 0;
        int min_len = INT_MAX;
        int res_start = 0;
        for (char c: target) {
            rec[c]++;
        }
        while (end < source.length()) {
            char c = source[end];
            rec[c]--;
            if (rec[c] >= 0) sum++;
            while (sum == target.length()) {
                if (end - start + 1 < min_len) {
                    min_len = end - start + 1;
                    res_start = start;
                }
                rec[source[start]]++;
                if (rec[source[start]] > 0) sum--;
                start++;
            }
            // } else {
            end++;
            // }
        }
        // return source.substr(res_start, min_len);
        if (min_len != INT_MAX) return source.substr(res_start, min_len);
        else return "";
    }
};